package com.study.demo1;


public class Test02 {
    public static void main(String args[]) {
        MyArray myArray = new MyArray(4);
        myArray.insert(24);
        myArray.insert(42);
        myArray.insert(52);
        myArray.insert(311);
        //count表示要选择几个数字
        int count = 3;
        long result = getBigNumber(myArray, count);
        System.out.println(result);
    }


    static long getBigNumber(MyArray a, int count) {
        a.quickSort();
        String str = "";
        int arrSize = a.getSize();
        for (int i=arrSize-1 ;i>arrSize-1-count;i--){
            long data = a.getData(i);
            str+=data;
        }
        long l = Long.parseLong(str);
        return l;
    }

    public static class MyArray {
        private long[] theArray;
        private int nElem;
        private int size;
        public MyArray(int size){
            theArray = new long[size];
            this.size =size;
            nElem = 0;
        }

        public void insert(long data){
            theArray[nElem] = data;
            nElem++;
        }


        public long getData(int index){
            return theArray[index];
        }

        public void display() {
            System.out.println("A = :");
            for (int i = 0; i < nElem; i++) {
                System.out.print(theArray[i] + "  ");
            }
            System.out.println("");


        }

        public int getSize() {
            return size;
        }


        public void quickSort() {
            recQuickSort(0, nElem - 1);
        }

        private void recQuickSort(int letf, int right) {                         //快速排序
            int size = right - letf + 1;
            if (size < 10) {
                insertSort(letf, right);
            } else {
                long mediaNumber = getMediaNumber(letf, right);
                int patation = patationIn(letf, right, mediaNumber);
                recQuickSort(letf, patation - 1);
                recQuickSort(patation + 1, right);
            }

        }

        private int patationIn(int letf, int right, long mediaNumber) {
            int letfPtr = letf;
            int rightPtr = right - 1;

            while (true) {
                while (theArray[++letfPtr] < mediaNumber) {
                    ;
                }

                while (theArray[--rightPtr] > mediaNumber) {
                    ;
                }

                if (rightPtr < letfPtr) {
                    break;
                } else {
                    swap(letfPtr, rightPtr);
                }
            }
            swap(letfPtr, right - 1);
            return letfPtr;
        }

        private long getMediaNumber(int letf, int right) {
            int center = (letf + right) / 2;
            if (theArray[letf] > theArray[center]) {
                swap(letf, center);
            }
            if (theArray[letf] > theArray[right]) {
                swap(letf, right);
            }
            if (theArray[center] > theArray[right]) {
                swap(center, right);
            }

            swap(center, right - 1);
            return theArray[right - 1];
        }

        private void swap(int letf, int right) {
            long temp = theArray[right];
            theArray[right] = theArray[letf];
            theArray[letf] = temp;

        }


        private void insertSort(int letf,int right) {

            int in, out;
            for (out = letf + 1; out <= right; out++) {
                long temp = theArray[out];
                in = out;
                while (in > letf && theArray[in - 1] > temp) {
                    theArray[in] = theArray[in - 1];
                    --in;
                }
                theArray[in] = temp;
            }
        }

    }}